package string;

/**
 * 91. Decode Ways
 *
 A message containing letters from A-Z is being encoded to numbers using the following mapping:

 'A' -> 1
 'B' -> 2
 ...
 'Z' -> 26
 Given a non-empty string containing only digits, determine the total number of ways to decode it.

 Example 1:

 Input: "12"
 Output: 2
 Explanation: It could be decoded as "AB" (1 2) or "L" (12).
 Example 2:

 Input: "226"
 Output: 3
 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
 */
public class Q91_NumDecoding {

    private int numDecodings(String s) {
        if ("".equals(s)) {
            return 0;
        }
        return selfCore(s);
    }
    /**
     * 我
     *  超时
     * 输入
     * 27
     * 010
     * 00
     * 12120
     *  1.非法输入
     *  2.其他情况
     * 思想
     *  for(i=0;<=1)
     *  截取字符串递归
     *
     */
    private int selfCore(String s) {
        if (s.startsWith("0")) {
            return 0;
        }
        if ("".equals(s) || s.length() == 1) {
            return 1;
        }
        int ans = 0;
        for (int i=0; i<=1 && i<s.length(); i++) {
            if (i == 1) {
                int ten = (s.charAt(i-1) - '0') * 10;
                int one = s.charAt(i) - '0';
                if (ten+one <= 0 || ten+one > 26) {
                    break;
                }
            }
            ans += selfCore(s.substring(i+1));
        }
        return ans;
    }

    /**
     * recursion
     */
    private int solveSelf(String s, int pos) {
        if (pos == s.length()) {
            return 1;
        }
        if (s.charAt(pos) == '0') {
            return 0;
        }
        int ans1 = solveSelf(s, pos+1);
        int ans2 = 0;
        if (pos < s.length()-1) {
            int ten = (s.charAt(pos) - '0') * 10;
            int one = s.charAt(pos+1) - '0';
            if (ten+one >= 1 && ten+one <= 26) {
                ans2 = solveSelf(s, pos+2);
            }
        }
        return ans1 + ans2;
    }

    /**
     * 从前向后 dp
     */
    private int solveDpArr(String s) {
        int[] dp = new int[s.length()+1];
        dp[0] = 1;//初始化-1位置为1
        if (s.charAt(0) == '0') {
            return 0;
        }
        dp[1] = 1;//c初始化第一个位置
        for (int i=1; i<=s.length()-1; i++) {
            int ans1 = 0;
            if (s.charAt(i) != '0') {
                ans1 = dp[i - 1 + 1];
            }
            int ans2 = 0;
            int ten = (s.charAt(i-1) - '0') * 10;
            int one = s.charAt(i) -'0';
            if (s.charAt(i-1) != '0' && ten + one <= 26) {
                ans2 = dp[i-2+1];
            }
            dp[i+1] = ans1 + ans2;
        }
        return dp[s.length()];
    }

    /**
     *
     * 思路
     *  12120
     *  1 cur=1 pre=1
     *  12 {"1,2","12"} cur=2 pre=1
     *  121 {"1,2,1","1,21","12,1"} cur=3 pre=2
     *  1212 {"1,2,1,2","12,12","1,21,2"} cur=5 pre=3
     *  12120 cur=pre
     */
    private int solveDp(String s) {
        if ("".equals(s) || s.startsWith("0")) {
            return 0;
        }
        int pre = 1, cur = 1;
        for (int i=1; i<s.length(); i++) {
            int tmp = cur;
            if (s.charAt(i) == '0') {
                if (s.charAt(i-1) == '1' || s.charAt(i-1) == '2') {
                    cur = pre;
                } else {
                    return 0;
                }
            } else if (s.charAt(i-1) == '1' || (s.charAt(i-1) == '2' && s.charAt(i) >= '1' && s.charAt(i) <= '6')) {
                cur += pre;
            }
            pre = tmp;
            //System.out.println(pre+" "+cur);
        }
        return cur;
    }

    public static void main(String[] args) {
        int res = new Q91_NumDecoding().numDecodings("12120");
        System.out.println("1:"+res);
        int res2 = new Q91_NumDecoding().solveDp("12120");
        System.out.println("2:"+res2);
        int res3 = new Q91_NumDecoding().solveSelf("12120", 0);
        System.out.println("3:"+res3);
        int res4 = new Q91_NumDecoding().solveDpArr("12120");
        System.out.println("4:"+res4);
    }
}
